import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: jzj
 * Date: 2024-03-24
 * Time: 23:47
 */
public class test_3 {
    public static int numDecodings1(String s) {
        //建立dp表
        char[] chs = s.toCharArray();
        int n = chs.length;
        int[] dp = new int[n];
        //
        if (chs[0] != '0') {
            dp[0] = 1;
        }
        if (n == 1) {
            return dp[0];
        }
        if (chs[0] != '0' && chs[1] != '0') {
            dp[1] += 1;
        }
        int t = (chs[0] - '0') * 10 + chs[1] - '0';
        if (t >= 10 && t <= 26) {
            dp[1] += 1;
        }
        for (int i = 2; i < n; i++) {
            if (chs[i] != '0') {
                dp[i] += dp[i - 1];
            }
            int m = (chs[i - 1] - '0') * 10 + chs[i] - '0';
            if (m >= 10 && m <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n - 1];
    }

    public int numDecodings2(String ss) {
        int n = ss.length();
        char[] s = ss.toCharArray();
        int[] dp = new int[n + 1];
        dp[0] = 1; // 保证后续填表是正确的
        if (s[1 - 1] != '0') dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            // 先处理第⼀种情况
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            // 处理第⼆种情况
            int tt = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if (tt >= 10 && tt <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];

    }

    public static void main(String[] args) {
        System.out.println(numDecodings1("2101"));

    }
}
